package com.xcc.dataStructures.demo09_tree;

/**
 * 二叉树
 *
 * @author xiaocheng
 * @date 2020/12/14 14:39
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        Node root = new Node(1,"宋江");
        Node node2 = new Node(2,"吴用");
        Node node3 = new Node(3,"卢俊义");
        Node node4 = new Node(4,"林冲");
        Node node5 = new Node(5,"关胜");
        root.setLeft(node2);
        root.setRight(node3);
        node3.setLeft(node5);
        node3.setRight(node4);

        BinaryTree binaryTree = new BinaryTree(root);
        System.out.println("===========前序遍历============");
        binaryTree.preOrderMng(); //1,2,3,5,4
        System.out.println();
        /*System.out.println("===========中序遍历============");
        binaryTree.midOrderMng(); //2,1,5,3,4
        System.out.println();
        System.out.println("===========后序遍历============");
        binaryTree.postOrderMng(); //2,5,4,3,1
        System.out.println();*/

        /*binaryTree.preSearch(1);
        binaryTree.midSearch(1);
        binaryTree.postSearch(1);*/

        binaryTree.del(3);
        System.out.println("===========删除节点后============");
        binaryTree.preOrderMng(); //1,2,3,5,4
        System.out.println();

    }
}


/**
 * 二叉树管理
 */
class BinaryTree{
    private Node root;

    public BinaryTree(Node root) {
        this.root = root;
    }

    /**
     * 删除节点
     */
    public void del(int no) {
        if (root == null) {
            System.out.println("当前二叉树为空!");
            return;
        }
        if (root.getNo() == no) {
            root = null;
            return;
        }
        root.del(no);
    }

    /**
     * 前序遍历
     */
    public void preOrderMng(){
        if (root == null) {
            System.out.println("当前二叉树为空!");
            return;
        }
        root.preOrder();
    }

    /**
     * 中序遍历
     */
    public void midOrderMng(){
        if (root == null) {
            System.out.println("当前二叉树为空!");
            return;
        }
        root.midOrder();
    }

    /**
     * 后序遍历
     */
    public void postOrderMng(){
        if (root == null) {
            System.out.println("当前二叉树为空!");
            return;
        }
        root.postOrder();
    }

    /**
     * 前序查找
     */
    public void preSearch(int no) {
        if (root == null) {
            System.out.println("当前二叉树为空!");
            return;
        }
        System.out.println(root.preSearch(no));
    }

    /**
     * 中序查找
     */
    public void midSearch(int no) {
        if (root == null) {
            System.out.println("当前二叉树为空!");
            return;
        }
        System.out.println(root.midSearch(no));
    }

    /**
     * 后序查找
     */
    public void postSearch(int no) {
        if (root == null) {
            System.out.println("当前二叉树为空!");
            return;
        }
        System.out.println(root.postSearch(no));
    }
}

/**
 * 节点
 */
class Node{
    //编号
    private int no;
    //名称
    private String name;
    //左子节点
    private Node left;
    //右子节点
    private Node right;

    /**
     * 删除节点
     */
    public void del(int no) {
        if (this.left != null) {
            if (this.left.no == no) {
                this.left = null;
                return;
            } else {
                this.left.del(no);
            }
        }
        if (this.right != null ) {
            if (this.right.no == no) {
                this.right = null;
                return;
            } else {
                this.right.del(no);
            }
        }
    }

    /**
     * 后序查找
     */
    public Node postSearch(int no) {
        Node node = null;
        if (this.left != null) {
            node = this.left.postSearch(no);
        }
        if (node != null) {
            return node;
        }
        if (this.right != null) {
            node = this.right.postSearch(no);
        }
        if (node != null) {
            return node;
        }
        System.out.println("后续查找");
        if (this.no == no) {
            return this;
        }
        return node;
    }

    /**
     * 中序查找
     */
    public Node midSearch(int no) {
        Node node = null;
        //先向左找
        if (this.left != null ) {
            node = this.left.midSearch(no);
        }
        //找到就返回
        if (node != null) {
            return node;
        }
        System.out.println("中序查找~");
        //找当前节点，找到返回
        if (this.no == no) {
            return this;
        }
        //向右找
        if (this.right != null) {
            node = this.right.midSearch(no);
        }
        return node;
    }

    /**
     * 前序查找
     */
    public Node preSearch(int no){
        System.out.println("前序查找~");
        if (this.no == no) {
            return this;
        }
        Node node = null;
        if (this.left != null) {
            node =  this.left.preSearch(no);
        }
        if (node != null) {
            return node;
        }
        if (this.right != null) {
            node =  this.right.preSearch(no);
        }
        return node;
    }

    /**
     * 前序遍历 : 根 -> 左 -> 右
     */
    public void preOrder(){
        if (this == null) {
            return;
        }
        if (this != null) {
            System.out.print(this.no + "\t");
        }
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历 : 左 -> 根 -> 右
     */
    public void midOrder(){
        if (this == null) {
            return;
        }
        if (this.left != null) {
            this.left.midOrder();
        }
        if (this != null) {
            System.out.print(this.no + "\t");
        }
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    /**
     * 后序遍历 : 左 -> 右 -> 根
     */
    public void postOrder(){
        if (this == null) {
            return;
        }
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        if (this != null) {
            System.out.print(this.no + "\t");
        }
    }

    public Node(int no,String name) {
        this.no = no;
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node[" +
                "no=" + no +
                ", name='" + name + '\'' +
                ']';
    }
}